﻿using System;
using System.Collections.Generic;
using STeaL.Algorithm;
using System.Diagnostics;

namespace STeaL.Collections.Generic {

  public class multiset_adaptor<T> : IList<T> {

    public multiset_adaptor(IList<T> list, Func<T,T,bool> pred) { 
      list_ = list; 
      pred_ = pred;
      list_.sort(pred_);
    }

    private IList<T> list_;
    private Func<T,T,bool> pred_;

    public void ReOrder(Func<T,T,bool> pred) {
      pred_ = pred;
      list_.sort(pred_);
    }

    public bool Find(T item, out Tuple<int,int> range) {
      range = list_.equal_range(item, pred_);
      return range.Item1 != range.Item2;
    }

    public int IndexOf(T item) { 
      int first = list_.lower_bound(item,pred_);
      return pred_(item, list_[first]) ? -1 : first;
    }

    public void Insert(int index, T item) {
      if ( (index > 0 && pred_(item, list_[index-1])) ||
           (index < list_.Count && pred_(list_[index],item)) ) {
        throw new ArgumentException("disordered insertion");
      }
      list_.Insert(index, item); 
      Debug.Assert(list_.is_sorted(pred_));
    }

    public void RemoveAt(int index) { list_.RemoveAt(index); }

    public T this[int index] { 
      get { return list_[index]; }
      set { if ( (index > 0 && pred_(value,list_[index-1])) ||
                 (index < list_.Count-1 && pred_(list_[index+1], value)) ) {
              throw new ArgumentException("disordered replacement");
            }
            list_[index] = value;
            Debug.Assert(list_.is_sorted(pred_));
          }
    }

    public void Add(T item) { list_.Insert(list_.upper_bound(item,pred_), item); }
    public void Clear() { list_.Clear(); }
    public bool Contains(T item) { return list_.binary_search(item,pred_); }
    public void CopyTo(T[] array, int arrayIndex) { list_.CopyTo(array, arrayIndex); }
    public int Count { get { return list_.Count;} }
    public bool IsReadOnly { get { return list_.IsReadOnly;} }

    public bool Remove(T item) {
      Tuple<int,int> range = list_.equal_range(item, pred_);
      list_.erase(range.Item1, range.Item2);
      return range.Item1 != range.Item2;
    }

    public IEnumerator<T> GetEnumerator() { return list_.GetEnumerator(); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return list_.GetEnumerator(); }

#if STL_COMPATIBLE
    public int insert(T item) {
      int pos = list_.upper_bound(item, pred_);
      list_.insert(pos, item);
      return pos;
    }

    public int insert(int pos, T item) {
      if ( (pos > 0 && pred_(item, list_[pos-1])) ||
           (pos <= list_.Count && pred_(list_[pos],item)) ) {
        pos = insert(item);
      } else {
        list_.Insert(pos, item);
      } 
      Debug.Assert(list_.is_sorted(pred_));
      return pos;
    }

    public void insert(IEnumerable<T> items) {
      foreach ( T item in items ) insert(item);
    }

    public int erase(T item) {
      Tuple<int,int> range = list_.equal_range(item, pred_);
      list_.erase(range.Item1, range.Item2);
      return range.Item2 - range.Item1;
    }

    public int find(T item) {
      Tuple<int,int> range = list_.equal_range(item, pred_);
      return range.Item1 == range.Item2 ? list_.end() : range.Item2;
    }
#endif      

  }

}
